package leetcode.violence;

public class leastMoney {
    public static void main(String[] args) {
        int arr[] = {1, 2, 4, 6, 9,};
        int aim = 10;
        System.out.println(process(arr, aim));
    }

    public static int process(int[] arr, int aim) {
        if (arr == null || aim < 0 || arr.length < 1) {
            return -1;
        }
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int k, int rest) {
        if (arr.length == k) {
            return rest == 0 ? 0 : -1;
        }
        int res = -1;
        for (int i = 0; i * arr[k] <= rest; i++) {
            int next = process(arr, k + 1, rest - i * arr[k]);
            if (next != -1) {
                res = res == -1 ? next + i : Math.min(res, next + i);
            }
        }
        return res;
    }
}
